1. Field of the Invention
This invention relates generally to information transfer systems that buffer information from multiple sources and particularly to a shared buffer architecture that dynamically allocates in a shared buffer pool a buffer size to each source depending on both the buffer pool utilization and the estimated offered load of each individual source.
2. Description of the Background Art
In general, network communication systems interconnect many users in a network. Each user is connected to the network at a port. The network is formed by the interconnection of many nodes where information input at an input port from one user at a source is passed from node to node through the network to an output port and to another user at a destination. The information transferred from source to destination is packetized and each node switches incoming packets at incoming ports to outgoing packets at outgoing ports. For ATM (Asynchronous Transfer Mode) networks, the packets are further divided into cells.
Using current technology, fast packet switches transfer hundreds of thousands of packets per second at every switch port. Each switch port is typically designed to transfer information at a rate from 50 Mbit/s to 2.4 Gbit/s for a broadband integrated service digital network (ISDN). Switch sizes range from a few ports to thousands of ports.
The term xe2x80x9cfast packet switchxe2x80x9d includes switches capable of handling both variable length packets and fixed length packets. Use of fixed-length packets can simplify the switch design. Fast packet switches using short, fixed-length packets (cells) are referred to as ATM switches. Fast packet switches handle different types of communications services in a single integrated network where such services may include voice, video and data communications. Since voice and video services can tolerate only a limited amount of delay and delay variance through a network, ATM switches are suitable for such services. The ATM standard for broadband ISDN networks defines a cell having a length of 53 bytes with a header of 5 bytes and data of 48 bytes. The ATM Forum Traffic Management Specification has specified a number of Service Class Definitions as follows:
CBR: Continuous Bit Rate. For real-time applications requiring tightly constrained delay and delay variation such as voice and video. The CBR service class requires the consistent availability of a fixed quantity of bandwidth.
RT-VBR: Realtime Variable Bit Rate. For applications where sources transmit at a rate which varies with time (referred to in the art as xe2x80x9cburstyxe2x80x9d), yet still must receive service with tightly constrained delay and delay variation.
NRT-VBR: Non-Realtime Variable Bit Rate. For bursty applications, having no service requirements related to delay or its variance, but having sensitivity to loss.
UBR: Unspecified Bit Rate. For non-real-time applications, such as file transfer and e-mail, that transmit non-continuous bursts of cells without related service guarantees and therefore without allocated bandwidth resource, without guarantee as to cell loss ratio or cell transfer delay, and without explicit feedback regarding current level of network congestion.
GFR: Guaranteed Frame Rate. Also for non-real-time applications, this service category provides loss guarantees for sources transmitting traffic at or below a contracted minimum rate. Once a source exceeds the contracted minimum rate, traffic above that rate does not receive any loss guarantees.
ABR: Available Bit Rate. For non-real-time applications that permit variation in information transfer rate depending on the amount of bandwidth available in the network.
In a typical ATM switch, the cell processing functions are performed within the nodes of a network. Each node is an ATM switch which includes input controllers (IC""s), a switch fabric (SF), output controllers (OC""s) and a node control (C). The node control is used for functions including connection establishment and release, bandwidth reservation, buffering control, congestion control, maintenance and network management.
In each switch, the input controllers are typically synchronized so that all cells from input controllers arrive at the switch fabric at the same time and cells can be accepted or rejected according to their priority. The traffic through the switch fabric is slotted and the switch fabric delay equals the sum of the timeslot duration, pipeline delay and the queuing delay.
The node control communicates with the input controllers and the output controllers either by a direct communication path which by-passes the switch fabric or via control cells transmitted through the switch fabric.
External connections to the switch are generally bi-directional. Bi-directional connections are formed by grouping an input controller (IC) and an output controller (OC) together to form a port controller (PC).
The input sequence of cells in a virtual channel is preserved across the switch fabric so that the output sequence of cells on each virtual channel is the same as the input sequence. Cells contain a virtual channel identifier (VCI) in the cell header which identifies the connection to which the cell belongs. Each incoming VCI in the header of each cell is translated in an input controller to specify the outgoing VCI identifier. This translation is performed in the input controller typically by table look-up using the incoming VCI to address a connection table. This connection table also contains a routing field to specify the output port of the switch fabric to which the connection is routed. Other information may be included in the connection table on a per connection basis such as the priority, class of service, and traffic type of the connection.
In an ATM switch, cell arrivals are not scheduled. In a typical operation, a number of cells may arrive simultaneously at different input ports, each requesting the same output port. Operations in which requests exceed the output capacity of the output port are referred to as output contention. Since an output port can only transmit a fixed number (for example, one) cell at a time, only the fixed number of cells can be accepted for transmission so that any other cells routed to that port must either be discarded or must be buffered in a queue. Different methods are employed for routing cells through a switch module, for example, self-routing and label routing.
A self-routing network operates with an input controller prefixing a routing tag to every cell. Typically, the input controller uses a table look-up from a routing table to obtain the routing tag. The routing tag specifies the output port to which the cell is to be delivered. Each switching element is able to make a fast routing decision by inspecting the routing tag. The self-routing network ensures that each cell will arrive at the required destination regardless of the switch port at which it enters.
A label routing network operates with a label in each cell referencing translation tables in each switching element. The label is translated in each switching element and hence any arbitrary network of switching elements may be employed.
Switches have two principal designs, time-division and space division. In a time-division switch fabric, all cells flow through a single communication channel shared in common by all input and output ports. In a space division switch, a plurality of paths are provided between the input and output ports. These paths operate concurrently so that many cells may be transmitted across the switch fabric at the same time. The total capacity of the switch fabric is thus the product of the bandwidth of each path and the average number of paths that can transmit a cell concurrently.
When the traffic load exceeds the available system resources in a network, congestion is present and performance degrades. When the number of cells is within the carrying capacity of the network, all cells can be delivered so that the number of cells delivered equals the number of cells sent without congestion. However, if cell traffic is increased to the level that nodes cannot handle the traffic, congestion results.
Congestion can be brought about by several factors. If nodes in a network are too slow to perform the various tasks required of them (queueing buffers, updating tables, etc.), queues build up, even though excess line capacity exists. On the other hand, even if nodes are infinitely fast, queues will build up whenever the input traffic rate exceeds the capacity of the output traffic rate for any particular group of outputs.
If a node has no free buffers for queueing cells, the node must discard newly arriving cells. For packet data traffic, when a cell is discarded, the packet from which the discarded cell came will be retransmitted, perhaps many times, further extending the congestion epoch.
Buffers are used in an ATM switch to receive and store incoming cells. A certain (fixed) amount of buffer space is reserved for CBR, RT-VBR, and NRT-VBR traffic. The required amount of space is known in advance because traffic from these service categories is policed at the receive side. However, ABR and UBR traffic are not well regulated and may overflow the remaining buffer space, resulting in loss of cells and degrading the quality of other connections.
The available art generally employs one of two buffer architectures. One buffer architecture uses a shared buffer space in which one high-volume connection can overflow the entire buffer leaving no buffer space for other connections. In another buffer architecture, an amount of buffer space is allocated for each connection so that it is often necessary to underutilize the buffer space to guard against overflow. This underutilization is costly since the allocated space is unused much of the time and is not used at all for connections that are not carrying traffic.
The present invention comprises a shared buffer architecture that dynamically allocates buffer size to each of multiple sources depending on both buffer pool utilization and the estimated offered load of each individual source. When the buffer pool is almost empty, each source is allocated a large buffer space. When the buffer pool is more full, each source is allocated a reduced buffer space, proportional to the weight of the individual connection.
The invention tracks the number of cells received per source and dynamically allocates a proportionate amount of buffer space in the buffer memory for that source. Dynamic allocation is made as a function of the fullness of the buffer memory allocation for all sources, in a manner that fairly allocates buffer space depending on the amount of traffic and the amount of buffer space taken up by each source, while providing some guaranteed buffer space for those connections which require explicit loss objectives. An advantage of the invention is therefore to provide an ability to control the relative fairness a given connection receives (relative to other connections within the same class of service). In operation, the memory allocation is readjusted depending on the total number of cells in the buffer memory.
The method and system of the invention therefore achieves a more efficient allocation whenever the buffer is not full. The upper limit on buffer size (a totally full buffer) is the same as with a fixed buffer, but otherwise the invention is more efficient than static buffer allocation because the available buffer space is optimized to allow each source to use as much buffer space as possible. To each source, the buffer appears larger than is actually available for all sources combined. The invention also enforces requirements, leading to more efficient use of the network, by ensuring that compliant sources are isolated from the effects of misbehavior of non-compliant sources.
A weighted fair discard operation is provided that is efficient over multiple hops. With fixed buffers the risk of discards in subsequent nodes increases exponentially with the number of hops. With dynamic allocation in the present invention, a decreased loss probability is achieved because the system tends to adjust to a steady-state condition, while retaining the ability to dynamically adapt to non-stationary loading patterns.
Although the present invention is particularly useful in ATM networks, other applications of the invention exist wherever shared buffering from multiple sources requires dynamic control.
The discard threshold can be changed to allocate different amounts of memory to the buffer depending on such factors as the quality of service desired, the relative weight within a given class of service, or the number of connections established within a given service class.
The problem of buffer overflow is greatest with UBR and GFR traffic, in which the source is unregulated. With these traffic types, expected to be the predominant type of traffic for several years to come, the effect of the invention is to control bandwidth (through the traffic management part of the system). Explicit forward congestion indication (EFCI) is preferably used to control the source rate.